<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Exercises
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora133.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora135.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Exercises</H2><A NAME="toc193"></A>
<H3> Association Lists</H3>In this first simple exercise, we will implement a polymorphic
abstract type for association lists, and present two different views
of the implementation.<BR>
<BR>
<OL type=1>
<LI> Define a signature <TT><A id="a251__1_APPEND/PMcor.ml.tex" href="javascript: void showMessage('1_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 1,APPEND/PMcor.ml.tex,ALIST -->ALIST</SPAN></A></TT> 
declaring an abstract type with two type parameters (one for the keys,
the other for the associated values), a creation function, an add
function, a lookup function, a membership test, and a deletion
function. <!-- POPUP DEFINITION -->
<layer id="l__1_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","1_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR><CODE> </CODE><B>module</B><CODE> </CODE><B>type</B><CODE> </CODE>ALIST<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>sig</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>create<CODE> </CODE><CODE>:</CODE><CODE> </CODE>unit<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>add<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'b</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>get<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><I>'b</I><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>mem<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>bool<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>rem<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>Characters 142-148:</CODE><BR><CODE>Syntax error</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("1_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script>The interface should be functional, <I>i.e.</I> without in-place modifications of the abstract type.<BR>
<BR>

<LI> Define a module <TT><A id="a252__2_APPEND/PMcor.ml.tex" href="javascript: void showMessage('2_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 2,APPEND/PMcor.ml.tex,Alist -->Alist</SPAN></A></TT> implementing the 
signature <TT>ALIST</TT>
<!-- POPUP DEFINITION -->
<layer id="l__2_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","2_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE>Alist<CODE>:</CODE>ALIST<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>*</CODE><I>'b</I><TT>)</TT><CODE> </CODE>list<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>create<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>add<CODE> </CODE>k<CODE> </CODE>v<CODE> </CODE>al<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>k<CODE>,</CODE>v<TT>)</TT>::al<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>get<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.assoc<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>mem<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.mem_assoc<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>rem<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.remove_assoc<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>Characters 14-19:</CODE><BR><CODE>Unbound module type ALIST</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("2_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define a signature <TT><A id="a253__3_APPEND/PMcor.ml.tex" href="javascript: void showMessage('3_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 3,APPEND/PMcor.ml.tex,ADM_ALIST -->ADM</SPAN></A>_ALIST</TT> 
for ``administrators'' of association lists. Administrators can only
create association lists, and add or remove entries from a list.
<!-- POPUP DEFINITION -->
<layer id="l__3_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","3_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE><B>type</B><CODE> </CODE>ADM_ALIST<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>sig</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>create<CODE> </CODE><CODE>:</CODE><CODE> </CODE>unit<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>add<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><I>'b</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>rem<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module type ADM_ALIST =</CODE><BR><CODE>  sig</CODE><BR><CODE>    type ('a, 'b) t</CODE><BR><CODE>    val create : unit -&gt; ('a, 'b) t</CODE><BR><CODE>    val add : 'a -&gt; 'b -&gt; ('a, 'b) t -&gt; ('a, 'b) t</CODE><BR><CODE>    val rem : 'a -&gt; ('a, 'b) t -&gt; ('a, 'b) t</CODE><BR><CODE>  end</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("3_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define a signature <TT><A id="a254__4_APPEND/PMcor.ml.tex" href="javascript: void showMessage('4_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 4,APPEND/PMcor.ml.tex,USER_ALIST -->USER</SPAN></A>_ALIST</TT> 
for ``users'' of association lists. Users can only perform lookups
and membership tests.
<!-- POPUP DEFINITION -->
<layer id="l__4_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","4_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE><B>type</B><CODE> </CODE>USER_ALIST<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>sig</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>get<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE><I>'b</I><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>mem<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>bool<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module type USER_ALIST =</CODE><BR><CODE>  sig</CODE><BR><CODE>    type ('a, 'b) t</CODE><BR><CODE>    val get : 'a -&gt; ('a, 'b) t -&gt; 'b</CODE><BR><CODE>    val mem : 'a -&gt; ('a, 'b) t -&gt; bool</CODE><BR><CODE>  end</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("4_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define two <A id="a255__5_APPEND/PMcor.ml.tex" href="javascript: void showMessage('5_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 5,APPEND/PMcor.ml.tex,AdmAlist_UserAlist -->modules</SPAN></A> <TT>AdmAlist</TT> and <TT>UserAlist</TT>  
for administrators and for users. Keep in mind that users must be
able to access lists created by administrators.
<!-- POPUP DEFINITION -->
<layer id="l__5_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","5_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE>AdmAlist<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>Alist<CODE>:</CODE>ADM_ALIST<CODE> </CODE><B>with</B><CODE> </CODE><B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>Alist.t<TT>)</TT><CODE> </CODE>;;<BR><CODE>Characters 20-25:</CODE><BR><CODE>Unbound module Alist</CODE><BR># <B>module</B><CODE> </CODE>UserAlist<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>Alist<CODE>:</CODE>USER_ALIST<CODE> </CODE><B>with</B><CODE> </CODE><B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>Alist.t<TT>)</TT><CODE> </CODE>;;<BR><CODE>Characters 20-25:</CODE><BR><CODE>Unbound module Alist</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("5_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script></OL><A NAME="toc194"></A>
<H3> Parameterized Vectors</H3>
This exercise illustrates the genericity and code reuse abilities of
parameterized modules. We will define a functor for manipulating
two-dimensional vectors (pairs of (<I>x</I>,<I>y</I>) coordinates) that can be
instantiated with different types for the coordinates.<BR>
<BR>
Numbers have the following signature:


<PRE><BR># <B>module</B><CODE> </CODE><B>type</B><CODE> </CODE>NUMBER<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>sig</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>a<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>create<CODE> </CODE><CODE>:</CODE><CODE> </CODE>a<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>add<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>string_of<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
<OL type=1>
<LI>
 Define the functor <TT><A id="a256__6_APPEND/PMcor.ml.tex" href="javascript: void showMessage('6_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 6,APPEND/PMcor.ml.tex,FVecteur -->FVector</SPAN></A></TT>, 
parameterized by a module of signature <TT>NUMBER</TT>,
and defining a type <I>t</I> of two-dimensional vectors over these numbers,
a creation function, an addition function, and a conversion to strings.
<!-- POPUP DEFINITION -->
<layer id="l__6_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","6_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE><CODE> </CODE>FVector<CODE> </CODE><TT>(</TT>N<CODE>:</CODE>NUMBER<TT>)</TT><CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE>N.t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>vx<CODE>:</CODE>e;<CODE> </CODE><B>mutable</B><CODE> </CODE>vy<CODE>:</CODE>e<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>create<CODE> </CODE>x0<CODE> </CODE>y0<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>vx<CODE>=</CODE>x0;<CODE> </CODE>vy<CODE>=</CODE>y0<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>add<CODE> </CODE>v1<CODE> </CODE>v2<CODE>=</CODE><CODE> </CODE><CODE> </CODE>{vx<CODE> </CODE><CODE>=</CODE><CODE> </CODE>N.add<CODE> </CODE>v1<CODE>.</CODE>vx<CODE> </CODE>v2<CODE>.</CODE>vx;<CODE> </CODE>vy<CODE> </CODE><CODE>=</CODE><CODE> </CODE>N.add<CODE> </CODE>v1<CODE>.</CODE>vy<CODE> </CODE>v2<CODE>.</CODE>vy}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>string_of<CODE> </CODE>v<CODE>=</CODE><CODE> </CODE><CODE>"("</CODE><CODE>^</CODE>N.string_of<CODE> </CODE>v<CODE>.</CODE>vx<CODE>^</CODE><CODE>" , "</CODE><CODE>^</CODE>N.string_of<CODE> </CODE>v<CODE>.</CODE>vy<CODE>^</CODE><CODE>")"</CODE><BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module FVector :</CODE><BR><CODE>  functor(N : NUMBER) -&gt;</CODE><BR><CODE>    sig</CODE><BR><CODE>      type e = N.t</CODE><BR><CODE>      and t = { mutable vx: e; mutable vy: e }</CODE><BR><CODE>      val create : e -&gt; e -&gt; t</CODE><BR><CODE>      val add : t -&gt; t -&gt; t</CODE><BR><CODE>      val string_of : t -&gt; string</CODE><BR><CODE>    end</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("6_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define a signature <TT><A id="a257__7_APPEND/PMcor.ml.tex" href="javascript: void showMessage('7_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 7,APPEND/PMcor.ml.tex,VECTEUR -->VECTOR</SPAN></A></TT>, 
without parameters, where the types of numbers and vectors are abstract.
<!-- POPUP DEFINITION -->
<layer id="l__7_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","7_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE><B>type</B><CODE> </CODE>VECTOR<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>sig</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>e<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>create<CODE> </CODE><CODE>:</CODE><CODE> </CODE>e<CODE> </CODE>-&gt;<CODE> </CODE>e<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>add<CODE> </CODE><CODE>:</CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>string_of<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module type VECTOR =</CODE><BR><CODE>  sig</CODE><BR><CODE>    type e</CODE><BR><CODE>    and t</CODE><BR><CODE>    val create : e -&gt; e -&gt; t</CODE><BR><CODE>    val add : t -&gt; t -&gt; t</CODE><BR><CODE>    val string_of : t -&gt; string</CODE><BR><CODE>  end</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("7_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define three <A id="a258__8_APPEND/PMcor.ml.tex" href="javascript: void showMessage('8_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 8,APPEND/PMcor.ml.tex,RatFloCom -->structures</SPAN></A> <TT>Rational</TT>, 
<TT>Float</TT> et <TT>Complex</TT> implementing the signature
<TT>NUMBER</TT>. 
<!-- POPUP DEFINITION -->
<layer id="l__8_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","8_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE>Rational<CODE>:</CODE>NUMBER<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>int<CODE>*</CODE>int<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>p<CODE>:</CODE>int;<CODE> </CODE>q<CODE>:</CODE>int<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>create<CODE> </CODE><TT>(</TT>p0<CODE>,</CODE>q0<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>p<CODE>=</CODE>p0;<CODE> </CODE>q<CODE>=</CODE>q0<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>add<CODE> </CODE>r1<CODE> </CODE>r2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE>r1<CODE>.</CODE>p<CODE>*</CODE>r2<CODE>.</CODE>q<CODE> </CODE><CODE>+</CODE><CODE> </CODE>r2<CODE>.</CODE>p<CODE>*</CODE>r1<CODE>.</CODE>q;<CODE> </CODE>q<CODE> </CODE><CODE>=</CODE><CODE> </CODE>r1<CODE>.</CODE>q<CODE>*</CODE>r2<CODE>.</CODE>q<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>string_of<CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>r<CODE>.</CODE>p<TT>)</TT><CODE>^</CODE><CODE>"/"</CODE><CODE>^</CODE><TT>(</TT>string_of_int<CODE> </CODE>r<CODE>.</CODE>q<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module Rational : NUMBER</CODE><BR><BR># <B>module</B><CODE> </CODE>Float<CODE>:</CODE>NUMBER<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>float<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>a<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>create<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>add<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>+.</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>string_of<CODE> </CODE><CODE>=</CODE><CODE> </CODE>string_of_float<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module Float : NUMBER</CODE><BR><BR># <B>module</B><CODE> </CODE>Complex<CODE>:</CODE>NUMBER<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>float<CODE>*</CODE>float<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>r<CODE>:</CODE>float;<CODE> </CODE>i<CODE>:</CODE>float<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>create<CODE> </CODE><TT>(</TT>r0<CODE>,</CODE><CODE> </CODE>i0<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>r<CODE>=</CODE>r0;<CODE> </CODE>i<CODE>=</CODE>i0<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>add<CODE> </CODE>c1<CODE> </CODE>c2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>c1<CODE>.</CODE>r<CODE>+.</CODE>c2<CODE>.</CODE>r;<CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>c1<CODE>.</CODE>i<CODE>+.</CODE>c2<CODE>.</CODE>i<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>string_of<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>string_of_float<CODE> </CODE>c<CODE>.</CODE>r<TT>)</TT><CODE>^</CODE><CODE>"+"</CODE><CODE>^</CODE><TT>(</TT>string_of_float<CODE> </CODE>c<CODE>.</CODE>r<TT>)</TT><CODE>^</CODE><CODE>"*i"</CODE><BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module Complex : NUMBER</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("8_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Use these structures to define (by functor application)
three <A id="a259__9_APPEND/PMcor.ml.tex" href="javascript: void showMessage('9_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 9,APPEND/PMcor.ml.tex,ModRatFloCom -->modules</SPAN></A> for vectors of rationals, reals 
and complex.
<!-- POPUP DEFINITION -->
<layer id="l__9_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","9_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE>RatVect<CODE>:</CODE>VECTOR<CODE> </CODE><CODE>=</CODE><CODE> </CODE>FVector<TT>(</TT>Rational<TT>)</TT><CODE> </CODE>;;<BR><CODE>module RatVect : VECTOR</CODE><BR># <B>module</B><CODE> </CODE>FloVect<CODE>:</CODE>VECTOR<CODE> </CODE><CODE>=</CODE><CODE> </CODE>FVector<TT>(</TT>Float<TT>)</TT><CODE> </CODE>;;<BR><CODE>module FloVect : VECTOR</CODE><BR># <B>module</B><CODE> </CODE>ComVect<CODE>:</CODE>VECTOR<CODE> </CODE><CODE>=</CODE><CODE> </CODE>FVector<TT>(</TT>Complex<TT>)</TT><CODE> </CODE>;;<BR><CODE>module ComVect : VECTOR</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("9_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script></OL><A NAME="toc195"></A>
<H3> Lexical Trees</H3>
This exercise follows up on the lexical trees introduced in
chapter <A HREF="index.html#chap-PF">2</A>, page <A HREF="book-ora020.html#exo-arbrlex">??</A>. The goal is to
define a generic module for handling lexical trees, parameterized by
an abstract type of words.<BR>
<BR>
<OL type=1>
<LI>
 Define the signature <TT><A id="a260__10_APPEND/PMcor.ml.tex" href="javascript: void showMessage('10_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 10,APPEND/PMcor.ml.tex,MOT -->WORD</SPAN></A></TT> defining 
an abstract type <I>alpha</I> for letters of the alphabet,
and another abstract type <I>t</I> for words on this alphabet.
Declare also the empty word, the conversion from an alphabet letter to
a one-letter word, the accessor to a letter of a word, the sub-word
operation, the length of a word, and word concatenation.
<!-- POPUP DEFINITION -->
<layer id="l__10_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","10_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE><B>type</B><CODE> </CODE>WORD<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>sig</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>alpha<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>null<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>of_alpha<CODE> </CODE><CODE>:</CODE><CODE> </CODE>alpha<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>get<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>int<CODE> </CODE>-&gt;<CODE> </CODE>alpha<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>sub<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>int<CODE> </CODE>-&gt;<CODE> </CODE>int<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>length<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>int<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>val</B><CODE> </CODE>concat<CODE> </CODE><CODE>:</CODE><CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module type WORD =</CODE><BR><CODE>  sig</CODE><BR><CODE>    type alpha</CODE><BR><CODE>    and t</CODE><BR><CODE>    val null : t</CODE><BR><CODE>    val of_alpha : alpha -&gt; t</CODE><BR><CODE>    val get : t -&gt; int -&gt; alpha</CODE><BR><CODE>    val sub : t -&gt; int -&gt; int -&gt; t</CODE><BR><CODE>    val length : t -&gt; int</CODE><BR><CODE>    val concat : t -&gt; t -&gt; t</CODE><BR><CODE>  end</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("10_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define the functor <TT><A id="a261__11_APPEND/PMcor.ml.tex" href="javascript: void showMessage('11_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 11,APPEND/PMcor.ml.tex,ArbLex -->LexTree</SPAN></A></TT>, 
parameterized by a module implementing <TT>WORD</TT>, that defines
(as a function of the types and operations over words) the type of
lexical trees and functions <TT>exists</TT>, <TT>insert</TT> et
<TT>select</TT> similar to those from chapter <A HREF="index.html#chap-PF">2</A>, page
<A HREF="book-ora020.html#exo-arbrlex">??</A>.
<!-- POPUP DEFINITION -->
<layer id="l__11_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","11_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE>LexTree<CODE> </CODE><TT>(</TT>W<CODE>:</CODE>WORD<TT>)</TT><CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>node<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Letter<CODE> </CODE><B>of</B><CODE> </CODE>W.alpha<CODE> </CODE><CODE>*</CODE><CODE> </CODE>bool<CODE> </CODE><CODE>*</CODE><CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>node<CODE> </CODE>list<BR><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>exist<CODE> </CODE>m<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>aux<CODE> </CODE>sm<CODE> </CODE>i<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<CODE> </CODE><TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<CODE> </CODE><B>when</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>W.get<CODE> </CODE>sm<CODE> </CODE>i<CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>then</B><CODE> </CODE>b<CODE> </CODE><B>else</B><CODE> </CODE>exist<CODE> </CODE><TT>(</TT>W.sub<CODE> </CODE>sm<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>l<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<CODE> </CODE><TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<CODE> </CODE><B>when</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>W.get<CODE> </CODE>sm<CODE> </CODE>i<CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>exist<CODE> </CODE>sm<CODE> </CODE>q<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE>m<CODE> </CODE><CODE>0</CODE><CODE> </CODE><TT>(</TT>W.length<CODE> </CODE>m<TT>)</TT><BR><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert<CODE> </CODE>m<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>aux<CODE> </CODE>sm<CODE> </CODE>i<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE>d<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>aux<CODE> </CODE><CODE>=</CODE><CODE> </CODE>insert<CODE> </CODE><TT>(</TT>W.sub<CODE> </CODE>sm<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>[]<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE>Letter<CODE> </CODE><TT>(</TT>W.get<CODE> </CODE>sm<CODE> </CODE>i<CODE>,</CODE><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE>,</CODE><CODE> </CODE>aux<TT>)</TT><CODE> </CODE><CODE>]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<CODE> </CODE><B>when</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>W.get<CODE> </CODE>sm<CODE> </CODE>i<CODE> </CODE>-&gt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE><B>true</B><CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>add<CODE> </CODE><TT>(</TT>W.sub<CODE> </CODE>sm<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>l<TT>)</TT>::q<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::<TT>(</TT>ajoute<CODE> </CODE>sm<CODE> </CODE>q<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE>m<CODE> </CODE><CODE>0</CODE><CODE> </CODE><TT>(</TT>W.length<CODE> </CODE>m<TT>)</TT><BR><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>select<CODE> </CODE>n<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<CODE> </CODE><B>when</B><CODE> </CODE>n<CODE>=</CODE><CODE>1</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>f<CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,_</CODE><TT>)</TT><TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>if</B><CODE> </CODE>b<CODE> </CODE><B>then</B><CODE> </CODE>W.of_alpha<CODE> </CODE>a<CODE> </CODE><B>else</B><CODE> </CODE>W.null<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.filter<CODE> </CODE><TT>(</TT><TT>(</TT><CODE>&lt;&gt;</CODE><TT>)</TT><CODE> </CODE>W.null<TT>)</TT><CODE> </CODE><TT>(</TT>List.map<CODE> </CODE>f<CODE> </CODE>d<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::q<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>select<CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>l<CODE> </CODE><B>and</B><CODE> </CODE>r2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>select<CODE> </CODE>n<CODE> </CODE>q<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pr<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE>W.concat<CODE> </CODE><TT>(</TT>W.of_alpha<CODE> </CODE>a<TT>)</TT><CODE> </CODE>s<TT>)</TT><CODE> </CODE>r<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>pr<CODE>@</CODE>r2<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>Characters 161-407:</CODE><BR><CODE>Warning: this pattern-matching is not exhaustive.</CODE><BR><CODE>Here is an example of a value that is not matched:</CODE><BR><CODE>_::_</CODE><BR><CODE>Characters 853-854:</CODE><BR><CODE>This expression has type t = node list but is here used with type W.t dlist</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("11_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Define the module <TT>Chars</TT> implementing the <TT>WORD</TT>
signature for the types <I>alpha = char</I> and <I>t = string</I>. 
Use it to obtain a module <TT><A id="a262__12_APPEND/PMcor.ml.tex" href="javascript: void showMessage('12_APPEND/PMcor.ml.tex')" class="mousable"><SPAN style=""><!-- 12,APPEND/PMcor.ml.tex,CharsDic -->CharDict</SPAN></A></TT>  
implementing dictionaries whose keys are character strings.
<!-- POPUP DEFINITION -->
<layer id="l__12_APPEND/PMcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","12_APPEND/PMcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>module</B><CODE> </CODE>Chars<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>struct</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>alpha<CODE> </CODE><CODE>=</CODE><CODE> </CODE>char<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>null<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>""</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>of_alpha<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>String.make<CODE> </CODE><CODE>1</CODE><CODE> </CODE>c<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>get<CODE> </CODE>s<CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE>s<CODE>.[</CODE>i<CODE>]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Invalid_argument<TT>(</TT><CODE>_</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE><TT>(</TT>Invalid_argument<CODE> </CODE><CODE>"Chars.get"</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>sub<CODE> </CODE>s<CODE> </CODE>i1<CODE> </CODE>i2<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE>String.sub<CODE> </CODE>s<CODE> </CODE>i1<CODE> </CODE>i2<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Invalid_argument<TT>(</TT><CODE>_</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE><TT>(</TT>Invalid_argument<CODE> </CODE><CODE>"Chars.sub"</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>length<CODE> </CODE><CODE>=</CODE><CODE> </CODE>String.length<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>concat<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE>^</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>module Chars :</CODE><BR><CODE>  sig</CODE><BR><CODE>    type alpha = char</CODE><BR><CODE>    and t = string</CODE><BR><CODE>    val null : string</CODE><BR><CODE>    val of_alpha : char -&gt; string</CODE><BR><CODE>    val get : string -&gt; int -&gt; char</CODE><BR><CODE>    val sub : string -&gt; int -&gt; int -&gt; string</CODE><BR><CODE>    val length : string -&gt; int</CODE><BR><CODE>    val concat : string -&gt; string -&gt; string</CODE><BR><CODE>  end</CODE><BR><BR># <B>module</B><CODE> </CODE>CharsDic<CODE> </CODE><CODE>=</CODE><CODE> </CODE>LexTree<TT>(</TT>Chars<TT>)</TT><CODE> </CODE>;;<BR><CODE>Characters 19-26:</CODE><BR><CODE>Unbound module LexTree</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("12_APPEND/PMcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script></OL><HR>
<A HREF="book-ora133.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora135.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
